package org.leetcode.easy.leetcode104;

import org.algorithm.Queue.LinkedListQueue;
import org.algorithm.Queue.Queue;
import org.leetcode.TreeNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;

public class Solution {


    public int maxDepth3(TreeNode root) {
        if (root==null){
            return 0;
        }

        int left = maxDepth3(root.left);
        int right = maxDepth3(root.right);

        return Math.max(left,right)+1;
    }

    /**
     * Button on up DFS
     */

    private int DFS(TreeNode root){
        if (root==null){
            return 0;
        }

        int left = DFS(root.left);
        int right = DFS(root.right);

        int currDepth =Math.max(left,right)+1;

        return currDepth;
    }



    /**
     * 递归遍历
     */
    public int maxDepth2(TreeNode root)
    {
        if (root==null) return 0;

        int leftMaxDepth = maxDepth2(root.left);
        int rightMaxDepth = maxDepth2(root.right);

        return Math.max(leftMaxDepth,rightMaxDepth)+1;
    }

    /**
     *层序遍历
     */
    public int maxDepth(TreeNode root) {

        if (root==null)
        {
            return 0;
        }

        int index = 0;

        Deque<TreeNode> deque = new LinkedList<>();

        deque.offer(root);

        while (!deque.isEmpty())
        {
            int length = deque.size();

            index++;

            while (length>0)
            {
                TreeNode tempNode = deque.pop();
                if (tempNode.right!=null) deque.add(tempNode.right);
                if (tempNode.left!=null) deque.add(tempNode.left);

                length--;

            }
        }
        return index;
    }

    public static void main(String[] args) {
        TreeNode leftLeaf = new TreeNode(3);
        TreeNode rightLeaf = new TreeNode(3);

        // 创建中间层节点
        TreeNode leftMid = new TreeNode(2, leftLeaf, null);
        TreeNode rightMid = new TreeNode(2, null, rightLeaf);

        // 创建根节点，使得整个二叉树对称
        TreeNode root = new TreeNode(1, leftMid, rightMid);

        Solution solution = new Solution();
        int maxDepth = solution.maxDepth(root);

        System.out.println(maxDepth);
    }
}
